package com.cheung.leetcode.hash;

import lyroot.entity.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class LC105 {


    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> hash = new HashMap<>();
        // 记录前序遍历中每个元素的在中序中下标，方便后面使用
        for (int i = 0; i < inorder.length; i++) {
            hash.put(inorder[i], i);
        }
        // 遍历每一个前序中的结点，设当前元素索引是root
        int root = 0;
        //  设left，right是root结点对应的子树在前序序列中的左右边界
        int left = 0;
        int right = preorder.length - 1;
        return next(hash, preorder, root, left, right);
    }

    public static TreeNode next(Map<Integer, Integer> hash, int[] preorder, int root, int left, int right) {
        if (left > right) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[root]);
        // 当前结点在中序中的索引为
        Integer i = hash.get(preorder[root]);
        // 当前结点的左结点就是左子树的根节点
        node.left = next(hash, preorder, root + 1, left, i - 1);
        // 当前结点的右结点就是右子树的根节点
        node.right = next(hash, preorder, i + 1 - left + root, i + 1, right);
        return node;
    }


    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7}, inorder = {9, 3, 15, 20, 7};
        buildTree(preorder, inorder);
    }
}
